A HashMap in Java is a part of the java.util package and is a commonly used collection class for storing key-value pairs. Internally, it uses a hashing mechanism to store and retrieve objects efficiently, providing an average time complexity of O(1) for basic operations like get(), put(), remove(), etc.

Here's how a HashMap works in Java:

  1. Key-Value Pair Storage:A HashMap stores data in the form of key-value pairs. Each key is unique, and each key maps to a corresponding value. You can store primitive data types and objects, but keys should implement the hashCode() and equals() methods appropriately.
  2. Hashing and Buckets:When you put a key-value pair into a HashMap, Java calculates the hash code of the key using the hashCode() method of the key object. This hash code determines which bucket the pair should be stored in.
    A bucket is essentially a slot in an internal array, and multiple keys may map to the same bucket (leading to collision). This array is called the table and its size is a power of 2 by default (initial size is 16).
  3. Index Calculation:After computing the hash code of the key, the HashMap applies a bitwise operation ((n-1) & hash) where n is the size of the table. This operation calculates the index at which the key-value pair should be stored in the array (bucket).
  4. Collision Handling:Two keys may generate the same hash code, or the hash code may map them to the same bucket. HashMap uses the following techniques to handle this collision:
    • Separate Chaining: Each bucket is essentially a linked list or a binary tree (since Java 8). If multiple keys map to the same bucket, they are stored as a chain (linked list) inside that bucket. When a bucket reaches a certain size, the list may be converted into a balanced binary tree to improve lookup time.
    • Open Addressing: In Java HashMap, collision is resolved primarily by chaining, but some implementations (like ConcurrentHashMap) might use other strategies.
  5. Retrieving Elements:When you call get(key):
    • The hash code of the key is computed, and the bucket index is calculated.
    • In that bucket, the equals() method is used to find the exact key among the possible collisions.
    • If the key is found, the corresponding value is returned; otherwise, null is returned.
  6. Resizing:As more elements are added to the HashMap, the load factor (default is 0.75) may exceed its threshold. When this happens, the table is resized (usually doubled in size), and all entries are rehashed and placed into the new table.

Example Code

Here’s a simple example of how to use a HashMap:

import java.util.HashMap;

public class HashMapExample {
    public static void main(String[] args) {
        // Create a HashMap
        HashMap map = new HashMap<>();
        
        // Add key-value pairs
        map.put("Alice", 30);
        map.put("Bob", 25);
        map.put("Charlie", 35);

        // Retrieve a value
        int age = map.get("Alice");
        System.out.println("Alice's age: " + age);

        // Check if a key exists
        if (map.containsKey("Bob")) {
            System.out.println("Bob exists in the map");
        }

        // Remove a key
        map.remove("Charlie");

        // Iterate over entries
        for (HashMap.Entry entry : map.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
    }
}

Key Points:

  • Time Complexity: O(1) on average for get() and put(), but in the worst case (with many collisions), it can degrade to O(n).
  • Load Factor: A value that controls resizing. A default load factor of 0.75 means the HashMap will resize when 75% of the array is filled.
  • Null Values: HashMap allows one null key and multiple null values.